//
// Created by francklinson on 2021/9/12 AT 9:20.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <stack>

using namespace std;

class Solution {
public:
    bool checkValidString(string s) {
        // 2个栈
        stack<int> leftStack;
        stack<int> starStack;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(')
                leftStack.push(i);
            else if (s[i] == '*')
                starStack.push(i);
            else {
                if (!leftStack.empty())
                    leftStack.pop();
                else if (!starStack.empty())
                    starStack.pop();
                else
                    // 两个栈里都没有东西了  这一个右括号没法匹配
                    return false;
            }
        }
        // 两个栈里面可能剩下字符，判断这些字符是否符合要求
        // 每个左括号都应该在*的左边(从右往左数)
        while (!leftStack.empty() and !starStack.empty()) {
            int leftIndex = leftStack.top();
            leftStack.pop();
            int starIndex = starStack.top();
            starStack.pop();
            if (leftIndex > starIndex)
                return false;
        }
        return leftStack.empty();
    }

    bool checkValidString2(string s) {
        // 用一个变量 记录（数量的上界和下界
        // 遇到( 上、下界+1
        // 遇到) 上 下界-1
        // 遇到* 上界+1 下界-1
        int minCount = 0, maxCount = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (c == '(') {
                minCount++;
                maxCount++;
            } else if (c == ')') {
                minCount = max(minCount - 1, 0);
                maxCount--;
                if (maxCount < 0) {
                    return false;
                }
            } else {
                minCount = max(minCount - 1, 0);
                maxCount++;
            }
        }
        return minCount == 0;

    }
};

int main() {
    Solution solution;
    cout << solution.checkValidString("(*****))") << endl;
    cout << solution.checkValidString("())") << endl;
    return 0;
}

